The primary objective of this multicenter, open-label Phase II study is to determine the tumor response of rhIL-12 administered by intravenous injection in patients with advanced malignant melanoma. Patients will continue therapy for a period of three multiple dose cycles or until there is disease progression or toxicity associated with rhIL-12. If the patient has an objective response or stable disease after three multiple dose cycles, therapy may be continued for a maximum of 15 multiple dose cycles of rhIL-12 treatment. Findings suggest that IL-12 is active against a variety of murine tumors and that multiple mechanisms may play a role in the antitumor activity of IL-12. The secondary objective is to assess the safety of this dose schedule and route of administration.